%a clear formalization of the problem: which methods, how and why
\section{Approach}\label{app}
This section deals with the approach to solve Sokoban boards. First the general idea is introduced. After this, different optimizations are explained to improve this idea.

\subsection{General idea}
The approach used was to explore a tree, which nodes consist of all possible board configurations, starting with the initial given board. This tree is implicitly searched, so it won't be completely stored in memory, by using BFS. In every step of the algorithm each box is pushed in four directions (up, down, left and right), as long as the move generates a valid board. Obviously there are many nodes for a given Sokoban board, so a tree of all possible configurations is extremely large. Because of the restriction to solve each board in one minute it is not viable to calculate all possible movements. Therefore it is necessary to find opportunities to prune the tree, and so be able to find a solution within the time limit. In the following sections the different pruning techniques are explained.

\subsection{The A* algorithm}
In order to visit as few nodes as possible, the algorithm tries to follow the edges that will presumably lead to a solution faster. This is achieved by selecting the nodes, instead of from a queue, from a priority queue that takes first the node with the least weight.

This weight is calculated using three components: the memory value, the heuristic value and a prize for boxes on goals.

The memory value consists of the size of the steps that have already been taken to reach the configuration being analysed. This will guarantee that the algorithm keeps moving on branches that have short paths.

Generally it is more useful to follow a branch of the movement tree that leads to a goal instead of leading away. Therefore every field of the sokoban board has a value which indicates how far it is away from the nearest goal (Look at picture \ref{pic/valueFields}). 
\begin{figure}[!htb]
\centering
\includegraphics[width=0.4\textwidth]{pics/valueFields}
\caption{Example for the heuristic values}
\label{pic/valueFields}
\end{figure}
While creating the movement tree the branch with the lowest value of the next field should be followed first. This is what we call the heuristic value. These values can be calculated once at the beginning, but they have to be updated every time a box is pushed on or away from a goal, because then there are more/less goals which influence the value of the fields.

Finally, every board is given a weight penalization for having boxes out of goals. This ensures that the agent will try to follow configurations that have many goals occupied.


\subsection{Duplicate positions}
Due to the way nodes are generated, it is possible that one or many of the sons of a configuration has already been explored before in the tree, therefore generating an excessive amount of calculations that have already been done. To solve this inconvenient, a Dynamic Programming approach was taken, in which every board generated was hashed and stored in a HashMap structure. This way, every time a new node was taken out of the BFS queue, we could efficiently check if it had already been analysed before. In case the node was present in the Hash, it was discarded, therefore saving a big amount of calculations.

\subsection{Detecting deadlocks}
A deadlock is a state of a Sokoban board that is not solvable any more. It is important to find as many deadlock states as possible to prune the movement tree.

We check for two different types of deadlocks: static and dynamic. 

Static deadlocks do not change and can be found during board initialization. An example of a static deadlock is when a box is pushed into the corner of two walls (Look at Figure \ref{pic/staticDeadlock}). 
\begin{figure}[!htb]
\centering
\includegraphics[width=0.4\textwidth]{pics/StaticDeadlock}
\caption{Example for a static deadlock}
\label{pic/staticDeadlock}
\end{figure}
In this situation the box cannot be moved and it is not on a goal, therefore its permanently stuck, making the board unsolvable. Even a whole row or column of a Sokoban board can be a deadlock when it is enclosed by walls and does not contain any goals. So a box on this row or column cannot be pushed on a goal any more. The algorithm for detecting static deadlocks is rather simple $\left[ 1\right]$: 

\begin{enumerate}
\item Delete all boxes from the board. 
\item Place a box at each goal square. 
\item "Pull" the box from the goal square to every reachable square and mark all reached squares as visited.
\end{enumerate}

Then we know that every unreachable square will lead to a deadlock. 

Detecting dynamic deadlocks is a lot trickier because they can appear during gameplay depending on the state of the boxes and player. A dynamic deadlock (Look at picture \ref{pic/dynamicDeadlock}) 

\begin{figure}[!htb]
\centering
\includegraphics[width=0.4\textwidth]{pics/dynamicDeadlock}
\caption{Example for a dynamic deadlock}
\label{pic/dynamicDeadlock}
\end{figure}

is, for example, a situation where two boxes are next to each other on the same row, which is next to a wall. So there is no possibility to push these two boxes any more.

\subsection{Tunnels}
A tunnel in a Sokoban board consists of some fields in a column or row that are surrounded by walls on both sides and have one or two entries/exits. This improvement deals with the fact that a box that has been pushed inside a tunnel (Look at Figure \ref{pic/tunnel}) must be pushed until the end of the tunnel before trying to search a  configuration that implies pushing any other box. So it is useful to push a box directly to the other end of the tunnel before doing anything else. In short, when a series of positions form a tunnel, they are treated as if they where one position.
\begin{figure}[!htb]
\centering
\includegraphics[width=0.4\textwidth]{pics/tunnel}
\caption{Example for a tunnel}
\label{pic/tunnel}
\end{figure}